package uestc.lj.basic.recall;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 打印一个字符串的所有子序列
 *
 * @Author:Crazlee
 * @Date:2021/11/25
 */
public class Code03_PrintAllSubsquences {
	public static void printAllSubsquences(String str) {
		char[] chs = str.toCharArray();
		process(chs, 0, new ArrayList<Character>());
	}

	/**
	 * 求解来到i位置的子序列
	 *
	 * @param chs    字符数组
	 * @param i      第i个位置
	 * @param result 之前选择所形成的列表
	 */
	public static void process(char[] chs, int i, List<Character> result) {
		if (i == chs.length) {
			printList(result);
			return;
		}
		//当选择第i个字符时，后续的选择
		List<Character> copyResult = copyList(result);
		copyResult.add(chs[i]);
		process(chs, i + 1, copyResult);

		//当不选择第i个字符时，后续的选择
		List<Character> copyResultWithNochar = copyList(result);
		process(chs, i + 1, copyResultWithNochar);

	}

	private static List<Character> copyList(List<Character> result) {
		return new ArrayList<>(result);
	}

	private static void printList(List<Character> result) {
		System.out.println(Arrays.toString(result.toArray()));
	}

	//=======================================================================================================================

	public static void printAllSubsqunences(String str) {
		char[] charArray = str.toCharArray();
		process(charArray, 0);
	}

	/**
	 * 优化
	 * @param charArray
	 * @param i
	 */
	public static void process(char[] charArray, int i) {
		if (i == charArray.length) {
			System.out.println(Arrays.toString(charArray));
		}
		process(charArray, i + 1);
		char temp = charArray[i];
		charArray[i] = 0;
		process(charArray, i + 1);
		charArray[i] = temp;
	}
}
